Modern high speed packet-based data communications networks, such as those employing Asynchronous Transfer Mode (ATM) technology, allow bandwidth to be reserved in advance. This is useful, in particular, for the transport of real time data such as voice or video. In ATM networks the requesting user must call the network control entity to set up a logical connection. Parameters are given in the call set up request which specify the required bandwidth. If all the requested parameters can be granted by the network controller the call is set up, otherwise it is refused.
An important problem in such networks is to ensure that traffic flowing in a particular network connection respects the bandwidth limits which were negotiated for that call at set up time. This is to guarantee that each connection only uses its share of the network resources, thereby minimizing the probability of lost data or other problems resulting from congestion in the network.
Data loss within the network must be avoided not only because missing information can alter the nature of the traffic—for example a missing cell can generate a glitch on a voice connection—but also because data loss can provoke data retransmission by higher level communications protocols thereby increasing the traffic on the connection and worsening network congestion—leading to a higher probability of further data loss.
To ensure that traffic within a connection conforms to its negotiated bandwidth parameters, traffic shaping or scheduling techniques have been developed for use at various points within the network in order to modify the flow of data within a connection to conform to its agreed parameters. Various policing schemes are also used in order to control and, if necessary, penalize traffic in the network by discarding cells from connections which try to exceed their allotted resources.
A wide variety of traffic shaping and policing methods have been proposed and studied. Many of these require a complex computation of an optimized cell transmission schedule. An example of such a technique can be found in EP-A-702472. This optimized transmission schedule must be recalculated if connections are added or deleted. Consequently, these methods are not easy to implement for use at the very high speeds required by modern networks.